package leetcode_动态规划._08买股票;

/**
 * @author yzh
 * @data 2021/3/21 15:46
 * 买卖股票的最佳时机
 * 买入和卖出只有一次
 * 思路：
 *   算出前 i 天的最大值
 *   找到数组中前 i 个最小的数即可
 */
public class _121 {
    public static void main(String[] args) {
        System.out.println(new _121().maxProfit_perfect(new int[]{7, 1, 5, 3, 6, 4}));
    }

    public int maxProfit(int[] prices) {
        int ans = 0;
        int[] dp = new int[prices.length];
        dp[0] = prices[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1], prices[i]);
            ans = Math.max(prices[i] - dp[i], ans);
        }
        return ans;
    }
    public int maxProfit_perfect(int[] prices) {
        int ans = 0, min = Integer.MAX_VALUE;
        for (int price : prices) {
            min = Math.min(min, price);
            ans = Math.max(ans, price - min);
        }
        return ans;
    }
}
